﻿#define _CRT_SECURE_NO_WARNINGS 1

//第2关：基于BF算法的网络入侵检测
//#include "iostream"
//#include "cstring"
//#include<stdlib.h>
//using namespace std;
//
//
//#define MAXLEN 5000			//串的最大长度
//typedef struct {
//	char* ch;			//存储串的一维数组
//	int length;				//串的当前长度   
//}HString;
//
//
//void InputRule(HString ip[], int n)
//{//输入n条规则，并将其中的n个ip地址存放到ip数组 
//	for (int i = 0; i < n; i++)
//		ip[i].ch = new char[100];
//	for (int i = 0; i < n; i++)
//	{
//		string ss;
//		int a, b;
//		getline(cin, ss);
//		for (int j = 0; j < (int)ss.length(); j++)
//		{
//			if (ss[j] == ':' && ss[j - 1] == 'p')
//				a = j + 1;
//			if (ss[j] == ' ' && ss[j + 1] == 'm')
//				b = j - 1;
//		}
//		for (int j = a, k = 0; j <= b; j++, k++)
//		{
//			ip[i].ch[k] = ss[j];
//			ip[i].length = b - a + 1;
//		}
//	}
//	
//
//}
//
//void InputLog(HString& log, int m)
//{//输入m条日志，并合并存放到log
//	delete log.ch;
//	log.ch = (char*)malloc(sizeof(char) * 10000);
//	string s;
//	for (int i = 0; i < m; i++)
//	{
//		string ss;
//		getline(cin, ss);
//		s += ss;
//	}
//	for (int i = 0; i < (int)s.length(); i++)
//		log.ch[i] = s[i];
//	log.length = (int)s.length();
//
//}
//
//int Index_BF(HString S, HString T)
//{//简单模式匹配算法,S为主串(目标串)，T为子串(模式串)。
////匹配成功返回主串中所含子串第一次出现的位置，否则返回-1。
//	int i = 0, j = 0;
//	while (i < S.length && j < T.length)
//	{
//		if (S.ch[i] == T.ch[j])
//		{
//			i++;
//			j++;
//		}
//		else
//		{
//			i = i - j + 1;
//			j = 0;
//		}
//	}
//	if (j >= T.length)
//		return i - T.length;
//	else return -1;
//
//}





//第3关：基于KMP算法的树种病毒检测

#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
#define MAXSIZE 2000

typedef struct
{
	char* ch;				//若是非空串，则按串长分配存储区，否则ch为NULL   
	int length;				//串的当前长度   
}HString;

int Index_KMP(HString S, HString T, int pos)
{//返回模式T在主串S中第pos个字符开始第一次出现的位置。若不存在，则返回值为0 
 //其中，T非空，1≤pos≤StrLength(S) 

}

bool Virus_detection(HString Virus, HString Tree)
{//判断是否匹配，如果可以，返回true，否则返回false 
//模式匹配算法调用Index_KMP函数 

}



//第4关：基于KMP算法的网络入侵检测

#include "iostream"
#include "cstring"
#include<stdlib.h>
using namespace std;


#define MAXLEN 5000			//串的最大长度
typedef struct {
	char* ch;			//存储串的一维数组
	int length;				//串的当前长度   
}HString;


void InputRule(HString ip[], int n)
{//输入n条规则，并将其中的n个ip地址存放到ip数组 

}

void InputLog(HString& log, int m)
{//输入m条日志，并合并存放到log，返回log的length

}

void GetNext(HString pattern, int* next)
{//求模式串pattern的next函数值并存入数组next

}

int Index_KMP(HString target, HString pattern, int* next)
{//KMP匹配算法,target为主串，pattern为子串。
//匹配成功返回主串中所含子串第一次出现的位置，否则返回-1。
//调用GetNext函数获取模式串的next数组

}






//第5关：基于BM算法的树种病毒检测

#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
#define MAXSIZE 2000

typedef struct
{
	char* ch;				//若是非空串，则按串长分配存储区，否则ch为NULL   
	int length;				//串的当前长度   
}HString;

int Index_BM(HString S, HString T, int pos)
{//返回模式T在主串S中第pos个字符开始第一次出现的位置。若不存在，则返回值为0 
 //其中，T非空，1≤pos≤StrLength(S) 

}

bool Virus_detection(HString Virus, HString Tree)
{//判断是否匹配，如果可以，返回true，否则返回false 
//模式匹配算法调用Index_KMP函数 

}








//第6关：基于BM算法的网络入侵检测

#include<iostream>
#include<string>
#include "cstring"
using namespace std;

#define ASCII_SIZE 256     //ASCII码共256位，可表示所有字符，作为坏字符数组的大小
#define MAXLEN 5000			//串的最大长度
typedef struct {
	char* ch;				   //存储串的一维数组
	int length;				   //串的当前长度   
}HString;

void InputRule(HString ip[], int n)
{//将输入的n个ip地址存放到ip数组

}

void InputLog(HString& log, int m)
{//将输入的m条日志合并存放到log，返回log的总长度

}

void getBC(HString pattern, int* bc)
{//得到坏字符bc数组

}

void getGS(HString pattern, int* suffix, bool* prefix)
{//得到好后缀gs，其中suffix为int类型数组存储后缀字符对应前面的位置，prefix为bool类型数组存储是否存在匹配的前缀字符串
//suffix和prefix共同构成好后缀数组

}

int getGSMove(int* suffix, bool* prefix, int bc_pos, int pattern_length)
{//利用suffix和prefix数组，返回好后缀移动的次数
//bc_pos表示坏字符BC的位置（后一位为好后缀起点位置）

}

int Index_BM(HString str, HString pattern)
{//在str.ch中匹配pattern.ch，匹配成功返回主串中所含子串第一次出现的位置，否则返回-1。
//分别求坏字符数组bc和好字符数组suffix、prefix，分别计算两个策略的移动位数，取大值作为最终移动位数

}





//第7关：统计字符出现的频度
//#include<iostream>
//#include<cstring>
//using namespace std;
//void Count(string c, int b[])
//{//统计字符出现的频度
//	for (int i = 0; i < 36; i++)
//		b[i] = 0;
//	for (int i = 0; c[i] != '\0'; i++)
//	{
//		if (c[i] >= '0' && c[i] <= '9')
//		{
//			int y = c[i] - '0';//转化为对应下标储存
//			b[y] = b[y] + 1;
//		}
//		else  //c[i]为字母时，ascii码还需另外减去7.
//		{
//			int y = c[i] - '0' - 7;
//			b[y] = b[y] + 1;
//		}
//	}
//	for (int i = 0; i < 36; i++)
//	{
//		if (b[i] == 0) 
//			continue;//b[i]=0时，则说明i对应的字符没有出现
//		else
//		{
//			if (i >= 0 && i <= 9)
//			{
//				char ch = i + '0';//转换为对应字符输出
//				cout << ch << ":" << b[i] << endl;
//			}
//			else
//			{
//				char ch = i + '0' + 7;
//				cout << ch << ":" << b[i] << endl;
//			}
//		}
//	}
//}





//第8关：递归实现字符串的逆序存储

//#include<iostream>
//#include<cstring>
//#define MAXSIZE 100
//using namespace std;
//void Reverse(char* a, int n)
//{//递归实现字符串的逆序存储
//	if (n <= 0) 
//		return;
//	char temp = a[0];
//	a[0] = a[n - 1];
//	a[n - 1] = temp;
//	Reverse(a + 1, n - 2);
//}





//第9关：字符串的插入
//#include<iostream>
//#define MAXSIZE 100
//using namespace std;
//void Insert(char s[], char t[], int pos, int LenS, int LenT)
//{//字符串的插入
//	pos = pos - 1;
//	for (int i = LenS - 1; i >= pos; i--)
//	{
//		s[i + LenT] = s[i];
//	}
//	for (int i = 0; t[i] != '\0'; i++, pos++)
//	{
//		s[pos] = t[i];
//	}
//	for (int i = 0; i <= LenS + LenT - 1; i++)
//	{
//		printf("%c", s[i]);
//	}
//	putchar('\n');
//}





//第10关：查找子串第一次出现的位置
#include<iostream>
#include<string.h>
using namespace std;
int strstr(string s1, string s2)
{//查找子串第一次出现的位置
	int len1 = s1.length();
	int len2 = s2.length();
	for (int i = 0; i <= len1 - len2; i++) {
		int j;
		for (j = 0; j < len2; j++) {
			if (s1[i + j] != s2[j]) {
				break;
			}
		}
		if (j == len2) {
			return i;
		}
	}
	return -1;
}